Structural decomposition methods have been developed for identifyingtractable classes of instances of fundamental problems in databases, such asconjunctive queries and query containment, of the constraint satisfactionproblem in artificial intelligence, or more generally of the homomorphismproblem over relational structures. Most structural decomposition methods canbe characterized through hypergraph games that are variations of the Robber andCops graph game that characterizes the notion of treewidth. In particular,decomposition trees somehow correspond to monotone winning strategies, wherethe escape space of the robber on the hypergraph is shrunk monotonically by thecops. In fact, unlike the treewidth case, there are hypergraphs where monotonicstrategies do not exist, while the robber can be captured by means of morecomplex non-monotonic strategies. However, these powerful strategies do notcorrespond in general to valid decompositions. The paper provides a general wayto exploit the power of non-monotonic strategies, by allowing a "disciplined"form of non-monotonicity, characteristic of cops playing in a greedy way. It isshown that deciding the existence of a (non-monotone) greedy winning strategy(and compute one, if any) is tractable. Moreover, despite theirnon-monotonicity, such strategies always induce valid decomposition trees,which can be computed efficiently based on them. As a consequence, greedystrategies allow us to define new islands of tractability for the consideredproblems properly including all previously known classes of tractableinstances.
展开▼
